/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


void reorderList(struct ListNode* head){
    if(head == NULL||head->next == NULL||head->next->next == NULL){
        return head;
    }
    struct ListNode* ss = head;
    struct ListNode* sp = head->next;
    while(1){
        ss = ss->next;
        sp = sp->next->next;
        if(sp == NULL||sp->next == NULL){
            break;
        }
    }
    struct ListNode* sf = ss->next;
    ss->next = NULL;
    struct ListNode* sk = sf;
    struct ListNode* sq = NULL;
    struct ListNode* sl = NULL;
    while(1){
        sp = sk->next;
        sk->next = sl;
        sl = sk;
        sk = sp;
        if(sk == NULL){
            break;
        }
    }
    struct ListNode* so = sl;
    struct ListNode* sg = head;
    struct ListNode* sv = NULL;
    struct ListNode* sw = NULL;
    while(1){
        sw = so;
        so = so->next;
        sv = head->next;
        head->next = sw;
        head = head->next;
        head->next = sv;
        head = head->next;
        if(so == NULL){
            break;
        }
    }    
}
